package com.heima.leetcode.practice;

import java.util.LinkedList;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 297. 二叉树的序列化与反序列化
 * @date 2025/3/18 12:04
 */
public class E297 {

    /**
     * <h3>方法一：使用层序遍历进行序列化</h3>
     *
     * @param root 树的根节点
     * @return 序列化后的字符串
     */
    public String serialize(TreeNode root) {
        // 1. 准备builder和队列
        StringBuilder builder = new StringBuilder();
        LinkedList<TreeNode> queue = new LinkedList<>();
        // 2. 初始化队列和builder
        queue.offer(root);
        builder.append("[");
        // 3. 开始层序遍历，遍历的时候null值也要遍历进去
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                // 3.1 如果队列中取出的元素为null，则直接添加null，并跳过本次循环
                if (poll == null) {
                    builder.append("null").append(",");
                    continue;
                }

                // 3.2 如果左子节点不为null，加入队列
                if (poll.left != null)
                    queue.offer(poll.left);
                    // 3.3 如果左子节点为null，将null值加入队列
                else queue.offer(null);
                // 可以简化：queue.offer(poll.left);

                // 3.4 如果右子节点不为null，加入队列
                if (poll.right != null)
                    queue.offer(poll.right);
                    // 3.5 如果右子节点为null，将null值加入队列
                else queue.offer(null);
                // 可以简化：queue.offer(poll.right);

                // 3.6 将当前队列中取到的节点值加入builder中
                builder.append(poll.val).append(",");
            }
        }
        // 4. 删除builder中最后一个逗号，并添加右括号，返回builder
        builder.setCharAt(builder.length() - 1, ']');
        return builder.toString();
    }

    /**
     * <h3>方法一：使用队列进行反序列化</h3>
     * @param data 序列化后的字符串
     * @return 反序列化后的根节点
     */
    @SuppressWarnings("all")
    public TreeNode deserialize(String data) {
        // 1. 将序列化的字符串转换为有效的数组（去除[和]和，）
        String[] values = data.substring(1, data.length() - 1).split(",");
        // 2. 如果第一个元素为null，则返回null
        if (values[0].equals("null")) return null;
        // 3. 准备根节点，准备队列，并加入根节点
        TreeNode root = new TreeNode(Integer.parseInt(values[0]));
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        // 4. 开始遍历
        for (int i = 1; i < values.length; i++) {
            // 4.1 跳过null值
            while (!queue.isEmpty() && queue.peek() == null)
                queue.poll();
            // 4.2 出队一个不为null的节点作为当前父节点
            TreeNode poll = queue.poll();
            // 4.3 构建左右子节点
            TreeNode left = values[i].equals("null") ?
                    null : new TreeNode(Integer.parseInt(values[i]));
            TreeNode right = values[i + 1].equals("null") ?
                    null : new TreeNode(Integer.parseInt(values[i + 1]));
            // 4.4 构建父子关系
            poll.left = left;
            poll.right = right;
            // 4.5 将左右子节点加入队列
            queue.offer(left);
            queue.offer(right);
            // 4.6 一次处理两回，i++
            i++;
        }
        return root;
    }
}
